package developer.算法.回溯.子集;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author zhangyongkang
 * @time 2025/4/1 16:17
 * @description 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * <p>
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 * 示例 2：
 * <p>
 * 输入：nums = [0]
 * 输出：[[],[0]]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 10
 * -10 <= nums[i] <= 10
 * nums 中的所有元素 互不相同
 */

public class ZiJi {

    public static void main(String[] args) {
        Solution4 solution = new Solution4();
        List<List<Integer>> subsets = solution.subsets(new int[]{1, 2, 3});
        for (List<Integer> subset : subsets) {
            System.out.println(Arrays.toString(subset.toArray()));
        }
    }


    static class Solution4 {
        List<List<Integer>> result;

        public List<List<Integer>> subsets(int[] nums) {
            result = new ArrayList<>();
            dfs(new ArrayList<>(), nums, 0);
            return result;
        }

        private void dfs(List<Integer> current, int[] nums, int start) {
            if (start == nums.length) {
                result.add(new ArrayList<>(current));
                return;
            }
            current.add(nums[start]);
            dfs(current, nums, start + 1);//考虑当前情况
            current.remove(current.size() - 1);
            dfs(current, nums, start + 1);//不考虑当前情况
        }
    }


    static class Solution3 {
        private List<List<Integer>> result;
        private List<Integer> current;

        public List<List<Integer>> subsets(int[] nums) {
            result = new ArrayList<>();
            current = new ArrayList<>();
            dfs(0, nums);
            return result;
        }

        private void dfs(
                int start,
                int[] nums
        ) {
            if (start == nums.length) {
                result.add(new ArrayList<>(current));
                return;
            }
            current.add(nums[start]);
            dfs(start + 1, nums);//考虑当前的值参current
            current.remove(current.size() - 1);
            dfs(start + 1, nums);//考虑当前的值不参与current
        }
    }


    static class Solution {
        List<List<Integer>> result;

        public List<List<Integer>> subsets(int[] nums) {
            result = new ArrayList<>();
            List<Integer> total = new ArrayList<>();

            for (int num : nums) {
                total.add(num);
            }
            Collections.sort(total);

            result.add(new ArrayList<>());//特殊情况处理
            callBack(0, total.size(), new ArrayList<>(), total);
            return result;
        }

        private void callBack(int start, int end, List<Integer> last, List<Integer> total) {
            if (start == end) {
                return;
            }
            for (int i = start; i < end; i++) {
                List<Integer> current = new ArrayList<>(last);
                current.add(total.get(i));
                result.add(current);
                callBack(i + 1, end, current, total);
            }
        }

    }

    static class SolutionOfficial {
        List<Integer> t = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        public List<List<Integer>> subsets(int[] nums) {
            dfs(0, nums);
            return ans;
        }

        public void dfs(int cur, int[] nums) {
            if (cur == nums.length) {
                ans.add(new ArrayList<Integer>(t));
                return;
            }
            t.add(nums[cur]);
            dfs(cur + 1, nums);//考虑选择当前位置
            t.remove(t.size() - 1);
            dfs(cur + 1, nums);//考虑不选择当前位置
        }
    }


}
